//
//  main.c
//  Questions
//
//  Created by wangrui on 14-09-16.
//  Copyright (c) 2014年 PPS. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

void printArray(int a[], int count)
{
	for (int k=0; k<count; k++) {
		printf("%d ",a[k]);
	}
	
	printf("\n");
}

void swap(int *a, int  *b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

void quickSort(int a[], int start, int end) {
	
	if (start >= end) {
		return;
	}
	
	int basic = a[start]; //设置第一个数为比较的基数
	
	int i = start; int j = end;
	
	while (i != j) {
		
		while (a[j] >= basic && j > i) {//从右向左找到小于基数的，指针指向这个位置
			j--;
		}
		
		while (a[i] <= basic && i < j) {//从左向右找到大于基数的，指针指向这个位置
			i++;
		}
		
		
		//交换
		if (i!=j) {
			swap(&a[i],&a[j]);
		}
		else {
			swap(&a[i],&a[start]);
		}
	}
	
	quickSort(a, start, i-1);
	quickSort(a, i+1, end);
}

int main(int argc, const char * argv[])
{
	int sorted[] = {5,7,9,10,2,4,5,6,7,100,22,53};
	
	quickSort(sorted, 0, 11);
	
	printArray(sorted, 12);
	
	return 0;
}


